class Gift {
public:
	int getValue(vector<int> gifts, int n) {				
		int i = 0;
		int j = 1;
		int temp = gifts[0];//初始化，temp先保存第一个数字
		int count = 1;//count初始化1，表示有1个相同的数字
		while (j<n)
		{
			if (count == 0)
			{				
				temp = gifts[j];
				count++;
				j++;
			}
			if (j >= n) 
				break;
			if (temp == gifts[j])
			{
				count++;
				j++;
			}
			else
			{
				count--;
				j++;
			}
		}

		if (count == 0) //count==0，不存在
		{
			return 0;
		}

		//但是count!=0，并不能说明不存在，因为我们要判断temp是不是有一半以上。
		count = 0;
		for (int i = 0; i < n; i++)
		{
			if (gifts[i] == temp)
				count++;
		}
		return (count > n / 2 ? temp : 0);
	}
};
